package com.example.programmerinterview;

import java.util.ArrayList;
import java.util.List;

/**
 * 面试题 08.09. 括号  同 22. 括号生成
 * 括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
 * <p>
 * 说明：解集不能包含重复的子集。
 * <p>
 * 例如，给出 n = 3，生成结果为：
 * <p>
 * [
 * "((()))",
 * "(()())",
 * "(())()",
 * "()(())",
 * "()()()"
 * ]
 * <p>
 * 思路：递归
 */
public class GenerateParenthesis {
    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        StringBuilder str = new StringBuilder();
        back(n, 0, 0, str);
        return res;
    }

    public void back(int n, int left, int right, StringBuilder str) {
        if (left + right == n * 2) {
            res.add(str.toString());
            return;
        }
        //递归左括号
        if (left < n) {
            str.append("(");
            back(n, left + 1, right, str);
            str.deleteCharAt(str.length() - 1);
        }
        //递归右括号
        if (right < left) {
            str.append(")");
            back(n, left, right + 1, str);
            str.deleteCharAt(str.length() - 1);
        }
    }
}